/**
 * @program: leetcode019
 * @author: JCM
 * @create: 2022-11-27 19:48
 * @description: 删除链表的倒数第 N 个节点
 **/

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class LeetCode019 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = 0;// 记录链表的总长度
        ListNode l = head;
        while(l != null) {
            l = l.next;
            len++;
        }
        // 如果链表长度小于 n 则说明找不到该节点，直接返回
        if(n > len) {
            return head;
        }

        ListNode prev = null;
        ListNode cur = head;
        // 找到所要删除的节点，cur 在该节点，prev 在此之前
        while(len > n) {
            prev = cur;
            cur = cur.next;
            len--;
        }
        if(prev != null) {
            prev.next = cur.next;
        }else {
            head = head.next;
        }
        return head;
    }

    public ListNode removeNthFromEnd2(ListNode head, int n) {
        // head前面存一个节点，当链表删空时，不必再做考虑
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode start = pre, end = pre;
        // 让 start 先走 n 步
        while(n != 0) {
            start = start.next;
            n--;
        }
        // 定位到要删除的节点
        while(start.next != null) {
            start = start.next;
            end = end.next;
        }
        end.next = end.next.next;
        return pre.next;
    }


}
